An integrated circuit (“IC”) is a device (e.g., a semiconductor device) that includes many electronic components, such as transistors, resistors, diodes, etc. These components are often interconnected to form multiple circuit components, such as gates, cells, memory units, arithmetic units, controllers, decoders, etc. An IC includes multiple layers of wiring that interconnect its electronic and circuit components. Traditionally, IC's use preferred direction (“PD”) wiring models, which specify a preferred wiring direction for each of their wiring layers. In preferred direction wiring models, the preferred direction typically alternates between successive wiring layers. One example of a PD wiring model is the PD Manhattan wiring model, which specifies alternating layers of preferred-direction horizontal and vertical wiring.
Wiring models have been proposed that allow wiring in diagonal directions (e.g., one wiring model allows wiring in horizontal, vertical, and ±45° diagonal directions). Some of these wiring models are non-preferred direction (“NPD”) wiring models. An NPD wiring model has at least one NPD wiring layer, on which two or more wiring directions are equally preferable and are at least as preferable as all other wiring directions on that layer.
Design engineers design IC's by transforming logical or circuit descriptions of the IC's into geometric descriptions, called layouts. IC layouts typically include (1) circuit modules (i.e., geometric representations of electronic or circuit IC components) with pins, and (2) interconnect lines (i.e., geometric representations of wiring) that connect the pins of the circuit modules. A net is typically defined as a collection of pins that need to be connected. A list of all or some of the nets in a layout is referred to as a net list.
To create layouts, design engineers typically use electronic design automation (“EDA”) applications. These applications provide sets of computer-based tools for creating, editing, and analyzing IC design layouts. One EDA tool is a router that defines routes for interconnect lines that connect the pins of nets.
In many EDA applications and other computer-aided design (“CAD”) applications, it is often necessary to obtain quickly a lower bound estimate of the distance between points in a layout. For instance, EDA routers often need to identify the actual distances or lower-bound distance estimates between routed and unrouted points in the layout. Some routers enumerate distances between routed and unrouted points to select successive points to route. Other routers have employed a variety of techniques to obtain lower-bound estimates. For example, some routers use a bounding-box technique to identify such estimates.
FIG. 1 presents one example that illustrates a bounding-box technique. This figure illustrates a point 105 and a set of points 110. All the points are part of a design layout 115. In this example, the set of points 110 includes points that have been routed, while the point 105 is a point that has not yet been routed. FIG. 1 also illustrates a rectangular bounding box 120 that encloses the set of points 110. The sides of this bounding box are parallel to the x- and y-coordinate axes of the layout's coordinate system 125. As shown in this figure, one lower-bound distance estimate between the point 105 and the set of points 110 is the Manhattan distance 130 between the point 105 and the bounding box 120. This lower-bound estimate is not a good estimate of the minimum distance from the point 105 to the set of points. The wide distribution of the set of points with respect to the x- and y-axes results in a large bounding box 120 that is not representative of the set of points. Also, the bounding box's position with respect to the external point 105 results in a poor estimated distance. Therefore, there is a need in the art for a method that generates better estimates of distances in design layouts. Also, there is a need to identify quickly the bounding polygon for a set of points.